package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
 */
class leetcode_236 {
    @Test
    fun test_1() {
        val root: TreeNode = TreeNode(3)
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        root.left = n5
        root.right = n1

        n5.left = n6
        n5.right = n2

        n2.left = n7
        n2.right = n4

        n1.left = n0
        n1.right = n8

        val actual = lowestCommonAncestor(root, n5, n1)
        val expect = root
        Assert.assertTrue(expect == actual)
    }

    @Test
    fun test_2() {
        val root: TreeNode = TreeNode(3)
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        root.left = n5
        root.right = n1

        n5.left = n6
        n5.right = n2

        n2.left = n7
        n2.right = n4

        n1.left = n0
        n1.right = n8

        val actual = lowestCommonAncestor(root, n5, n4)
        val expect = n5
        Assert.assertTrue(expect == actual)
    }

    @Test
    fun test_3() {
        val root: TreeNode = TreeNode(1)
        val n2 = TreeNode(2)
        root.left = n2

        val actual = lowestCommonAncestor(root, root, n2)
        val expect = root
        Assert.assertTrue(expect == actual)
    }
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        /*
        1 提示很重要：
            所有 Node.val 互不相同 。
            p != q
            p 和 q 均存在于给定的二叉树中。
        2 求公共祖先，要用后序遍历（即回溯）实现从底向上的遍历方式。

        3 找到 p 和 q 相等的节点left，right，当left 和 right 均不为空时，那么，root 就是最近公共祖先。
         */

        // 深度遍历 - 后序遍历 - 递归
        // T - N
        // S - N

        // 结束条件
        if (null == root || null == p || null == q) {
            return null
        }
        if (root.`val` == p.`val` || root.`val` == q.`val`) {
            return root
        }

        // 左
        val left: TreeNode? = lowestCommonAncestor(root.left, p, q)


        // 右
        val right: TreeNode? = lowestCommonAncestor(root.right, p, q)

        // 中 - 回溯过程
        if (null != left && right != null) {
            return root
        } else if (null != left && right == null) {
            return left
        } else if (null == left && right != null) {
            return right
        } else { // null == left && null == right
            return null
        }
    }
}